
class Solution {
    public int[] printNumbers(int n) {
        int result = 0;
        int[] resultNums = new int[(int)Math.pow(10,n)-1];
        for(int i=0 ; i<resultNums.length;i++){
            resultNums[i] = i+1;
        }
        return resultNums;
    }
}
class CQueue {

    var stack1: [Int] = []
    var stack2: [Int] = []

    init() {

    }
    
    func appendTail(_ value: Int) {
        stack1.append(value)
    }
    
    func deleteHead() -> Int {
        if stack2.isEmpty {
            while let head = stack1.popLast() {
                stack2.append(head)
            }
        }
        return stack2.popLast() ?? -1
    }
}

class Solution {
    func findSolution(_ customfunction: CustomFunction, _ z: Int) -> [[Int]] {
        var result: [[Int]] = []
        var x = 1
        var y = 1000
        var tz = 0
        while x <= 1000, y >= 1 {
            tz = customfunction.f(x, y)
            if tz == z {
                result.append([x, y])
                x += 1
                y -= 1
            } else if tz > z {
                y -= 1
            } else {
                x += 1
            }
        }
        return result
    }
}
class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        var k = 0
        for i in 0..<nums.count {
            if i > k {
                return false
            }
            k = max(k, i + nums[i])
        }
        return true
    }
}
class Solution {
    func longestPalindrome(_ s: String) -> String {
        if s.count < 2 {
            return s
        }
        var start = 0
        var end = 0
        var array = s.map({ String.init($0)})
        for i in 0 ..< s.count {
            let len1 = expandCenter(array: array, left: i, right: i)
            let len2 = expandCenter(array: array, left: i, right: i + 1)
            let len = max(len1, len2)
            if(len > end - start) {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }
        array.removeFirst(start)
        let sub = array.prefix(end - start + 1).joined()
        return sub
    }
    func expandCenter(array: [String], left: Int, right: Int) -> Int {
        var l = left
        var r = right
        while l >= 0 && r < array.count && array[l] == array[r] {
            l -= 1
            r += 1
        }
        return r - l - 1
    }
}

var ans = [String]()

func generateParenthesis(_ n: Int) -> [String] {
    fork(left: n, right: n, current: "")
    return ans
}

func fork(left: Int, right: Int, current: String) {
    if right > 0 {
        if left > 0 {
            fork(left: left - 1, right: right, current: current + "(")
        }
        if right > left {
            fork(left: left, right: right - 1, current: current + ")")
        }
    } else {
        ans.append(current)
    }
}

///
///回文数 2月2日 18:27
class Solution {
    func isPalindrome(_ x: Int) -> Bool {
        var y = x
        var z = 0
        while(y>0){
            let a = y/10
            let b = y%10
            z = b + z * 10
            y = a
        }
        if z == x {
            return true
        } else {
            return false
        }
    }
}
/// 删除多余元素 2月3日 17:44
class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        var b:Int?
        var result = 0
        var index = 0
        for value in nums {
            if value == b {
                let index = nums.firstIndex(of: value)!
                nums.remove(at:index)
            } else {
                b = value
                result += 1
            }
            index = index + 1
        }
        return result
    }
    /// 双指针
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        if nums.count == 0 {
            return nums
        }
        var left = 0
        var right = 1
        while right < nums.count {
            if nums[left] != nums[right] {
                left += 1
                nums[left] = nums[right]
            }
            right += 1
        }
        return left + 1
    }
}

/// 二叉树是否对称
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return isMirror(root, root)
    }
    
    func isMirror(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
        if left == nil && right == nil {
            return true
        }
        if left == nil || right == nil {
            return false
        }
        if (left!.val != right!.val) {
            return false
        }
        return isMirror(left!.left, right!.right) && isMirror(left!.right, right!.left)
    }
}

class Solution {
    func getRow(_ rowIndex: Int) -> [Int] {
        if rowIndex == 0 {
            return [1]
        }
        var row = [Int]()
        row.append(1)
        
        for i in 1...rowIndex {
            row.append(Int(row[i-1] * (rowIndex-i+1) / i))
        }
        return row
    }
}
class Solution {
    func getRow(_ rowIndex: Int) -> [Int] {
        let arry = [[1],
                    [1,1],
                    [1,2,1],
                    [1,3,3,1],
                    [1,4,6,4,1],
                    [1,5,10,10,5,1],
                    [1,6,15,20,15,6,1],
                    [1,7,21,35,35,21,7,1],
                    [1,8,28,56,70,56,28,8,1],
                    [1,9,36,84,126,126,84,36,9,1],
                    [1,10,45,120,210,252,210,120,45,10,1],
                    [1,11,55,165,330,462,462,330,165,55,11,1],
                    [1,12,66,220,495,792,924,792,495,220,66,12,1],
                    [1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1],
                    [1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1],
                    [1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1],
                    [1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1],
                    [1,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1],
                    [1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1],
                    [1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1],
                    [1,20,190,1140,4845,15504,38760,77520,125970,167960,184756,167960,125970,77520,38760,15504,4845,1140,190,20,1],
                    [1,21,210,1330,5985,20349,54264,116280,203490,293930,352716,352716,293930,203490,116280,54264,20349,5985,1330,210,21,1],
                    [1,22,231,1540,7315,26334,74613,170544,319770,497420,646646,705432,646646,497420,319770,170544,74613,26334,7315,1540,231,22,1],
                    [1,23,253,1771,8855,33649,100947,245157,490314,817190,1144066,1352078,1352078,1144066,817190,490314,245157,100947,33649,8855,1771,253,23,1],
                    [1,24,276,2024,10626,42504,134596,346104,735471,1307504,1961256,2496144,2704156,2496144,1961256,1307504,735471,346104,134596,42504,10626,2024,276,24,1],
                    [1,25,300,2300,12650,53130,177100,480700,1081575,2042975,3268760,4457400,5200300,5200300,4457400,3268760,2042975,1081575,480700,177100,53130,12650,2300,300,25,1],
                    [1,26,325,2600,14950,65780,230230,657800,1562275,3124550,5311735,7726160,9657700,10400600,9657700,7726160,5311735,3124550,1562275,657800,230230,65780,14950,2600,325,26,1],
                    [1,27,351,2925,17550,80730,296010,888030,2220075,4686825,8436285,13037895,17383860,20058300,20058300,17383860,13037895,8436285,4686825,2220075,888030,296010,80730,17550,2925,351,27,1],
                    [1,28,378,3276,20475,98280,376740,1184040,3108105,6906900,13123110,21474180,30421755,37442160,40116600,37442160,30421755,21474180,13123110,6906900,3108105,1184040,376740,98280,20475,3276,378,28,1],
                    [1,29,406,3654,23751,118755,475020,1560780,4292145,10015005,20030010,34597290,51895935,67863915,77558760,77558760,67863915,51895935,34597290,20030010,10015005,4292145,1560780,475020,118755,23751,3654,406,29,1],
                    [1,30,435,4060,27405,142506,593775,2035800,5852925,14307150,30045015,54627300,86493225,119759850,145422675,155117520,145422675,119759850,86493225,54627300,30045015,14307150,5852925,2035800,593775,142506,27405,4060,435,30,1],
                    [1,31,465,4495,31465,169911,736281,2629575,7888725,20160075,44352165,84672315,141120525,206253075,265182525,300540195,300540195,265182525,206253075,141120525,84672315,44352165,20160075,7888725,2629575,736281,169911,31465,4495,465,31,1],
                    [1,32,496,4960,35960,201376,906192,3365856,10518300,28048800,64512240,129024480,225792840,347373600,471435600,565722720,601080390,565722720,471435600,347373600,225792840,129024480,64512240,28048800,10518300,3365856,906192,201376,35960,4960,496,32,1],
                    [1,33,528,5456,40920,237336,1107568,4272048,13884156,38567100,92561040,193536720,354817320,573166440,818809200,1037158320,1166803110,1166803110,1037158320,818809200,573166440,354817320,193536720,92561040,38567100,13884156,4272048,1107568,237336,40920,5456,528,33,1]]
        return arry[rowIndex]
    }
}
// 判断两个树是否相同
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p == nil && q == nil {
            return true
        }
        return p?.val == q?.val &&
        isSameTree(p?.left, q?.left) &&
        isSameTree(p?.right, q?.right)
    }
}
// 合并两个有序数组
class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var mRight = m - 1
        var nRight = n - 1
        while nRight >= 0 {
            if mRight >= 0 && nums1[mRight] > nums2[nRight] {
                nums1[mRight + nRight + 1] = nums1[mRight]
                mRight -= 1
            } else {
                nums1[mRight + nRight + 1] = nums2[nRight]
                nRight -= 1
            }
        }
    }
}
// 快乐数：双指针
class Solution {
    func isHappy(_ n: Int) -> Bool {
        var slowPointer = n
        var fastPointer = n
        var count = 0
        while (fastPointer != slowPointer || count == 0) {
            count = count + 1
            fastPointer = next(fastPointer)
            fastPointer = next(fastPointer)
            slowPointer = next(slowPointer)
        }
        if fastPointer == 1 {
            return true
        }
        return false
    }
    func next(_ n:Int) -> Int {
        var value = n
        var relust = 0
        while value > 0 {
            let v = value%10
            value = value/10
            relust = relust + v*v
        }
        return relust
    }
}
// 递归
class Solution {
    var set: Set<Int> = []
    func isHappy(_ n: Int) -> Bool {
        if set.contains(n) {
            return false
        }
        set.insert(n)
        var value = n
        var relust = 0
        while value > 0 {
            let v = value%10
            value = value/10
            relust = relust + v*v
        }
        if relust == 1 {
            return true
        }
        return isHappy(relust)
    }
}
// 链表反转
class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil {
            return nil
        }
        var result:ListNode?
        var chang = head
        var tem:ListNode?
        while chang != nil {
            tem = chang?.next
            chang?.next = result
            result = chang
            chang = tem
        }
        return result
    }
}
// 2月07
// 青蛙跳台阶，动态分布
class Solution {
    func numWays(_ n: Int) -> Int {
        if n == 1 || n == 0 {
            return 1
        }
        if n == 2 {
            return 2
        }
        var k = 3
        var result = 3
        var a = 2
        var b = 3
        while k != n {
            result = (a + b)%1000000007
            a = b
            b = result
            k = k + 1
        }
        return result
    }
}

// 从尾到头打印链表
class Solution {
    // 数组查元素，效率低
    func reversePrint(_ head: ListNode?) -> [Int] {
        var ary:Array<Int> = []
        var changeValue = head
        while changeValue != nil {
            ary.insert(changeValue!.val, at: 0)
            changeValue = changeValue?.next
        }
        return ary
    }
}

class Solution {
    // 反转链表添加元素，效率高
    // append,方法比insert方法效率高原因是，数组相当于是一个栈
    // insert是会移动插入位置时候的元素，
    // append只会有入栈操作。因此apend效率要高
    func reversePrint(_ head: ListNode?) -> [Int] {
        var ary:Array<Int> = []
        var changeValue = head
        var reset:ListNode?
        var temp:ListNode?
        while changeValue != nil {
            temp = changeValue?.next
            changeValue?.next = reset
            reset = changeValue
            changeValue = temp
        }
        while reset != nil {
            ary.append(reset!.val)
            reset = reset?.next
        }
        return ary
    }
}
/// 检测链表是否有环
class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var changeHead = head
        var first = head
        var slow = head
        while (first?.next != nil) {
            first  = next(first)
            first = next(first)
            slow = next(slow)
            if slow === first {
                return true
            }
        }
        return false
    }
    func next(_ list:ListNode?) -> ListNode? {
        return list?.next
    }
}
/// 圆圈剩下的最后一个数
class Solution {
    func lastRemaining(_ n: Int, _ m: Int) -> Int {
        var result = 0
        for i in 2 ... n {
            result = (m + result) % i
        }
        return result
    }
}
/// 剑指 Offer 11. 旋转数组的最小数字
class Solution {
    func minArray(_ numbers: [Int]) -> Int {
        if numbers.count == 0 {
            return 0
        }
        var i = 0
        var j = numbers.count - 1
        var temp = 0
        while j > i {
            temp = (i + j) / 2
            if numbers[temp] < numbers[j]  {
                j = temp
            } else if numbers[temp] > numbers[j] {
                i = temp + 1
            } else {
                j -= 1
            }
        }
        return numbers[i]
    }
}

class Solution {
    func deleteNode(_ head: ListNode?, _ val: Int) -> ListNode? {
        var changeList = head
        var temp:ListNode? = head
        var result:ListNode? = temp
        if changeList?.val == val {
            return changeList?.next
        }
        while changeList?.val != val {
            changeList = changeList?.next
            if changeList?.val != val {
                temp = temp?.next
            }
        }
        temp?.next = changeList?.next
        return result
    }
}

class Solution {
    func cuttingRope(_ n: Int) -> Int {
        if n <= 3 {
            return n - 1
        }
        var k = n / 3
        var d = n % 3
        var max = 1
        for i in 0...k-1 {
            max = max * 3
        }
        if d == 1 {
            max = max/3*4
        } else if d != 0 {
            max = max*d
        }
        return max
    }
}

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1 = l1
        var l2 = l2
        var l3: ListNode? = l1
        var l4: ListNode? = l3
        var add = 0
        while l1 != nil {
            if l1!.val + (l2?.val ?? 0) + add >= 10 {
                l3?.val = l1!.val + (l2?.val ?? 0) + add - 10
                add = 1
            } else {
                l3?.val = l1!.val + (l2?.val ?? 0) + add
                add = 0
            }
            l3 = l3?.next != nil ? l3?.next : l3
            l1 = l1?.next
            l2 = l2?.next
        }
        if  l2 != nil {
            l3?.next = l2
            l3 = l3?.next
            while l2 != nil {
                if l2!.val + add >= 10 {
                    l3?.val = (l2!.val + add) - 10
                    add = 1
                } else {
                    l3?.val = l2!.val + add
                    add = 0
                }
                l3 = l3?.next != nil ? l3?.next : l3
                l2 = l2?.next
                if add == 0 {
                    return l4
                }
            }
        }
        if add == 1 {
            l3?.next = ListNode(1)
            l3 = l3?.next
        }
        return l4
    }
}
//  2月12 最大无重复字符
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var setA:Array = Array<Character>()
        var result = 0
        var change = 0
        for i in s {
            if !setA.contains(i) {
                setA.append(i)
                change = setA.count
                if change > result {
                    result = change
                }
            } else {
                var k = setA.first
                while k != i {
                    setA.removeFirst()
                    k = setA.first
                }
                setA.removeFirst()
                setA.append(i)
                change = setA.count
                if change > result {
                    result = change
                }
                change = 1
            }
        }
        if change > result {
            result = change
        }
        return result
    }
}
// 递归快次幂
class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        if n == 0 {
            return 1
        } else if n < 0 {
            return 1 / myPow(x, -n)
        } else if n % 2 == 1 {
            return x * myPow(x, n-1)
        } else {
            return myPow(x*x, n/2)
        }
    }
}
class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        if preorder.count == 0 {
            return nil
        }
        
        if preorder.count == 1 {
            return TreeNode.init(preorder[0])
        }
        
        let rootValue = preorder[0]
        
        var preorderLeft:[Int] = []
        var preorderRight:[Int] = []
        var inorderLeft:[Int] = []
        var inorderRight:[Int] = []
        
        var flag = -1; // -1代表现在是左子树的元素，1代表现在是右子树的元素
        for num in inorder {
            if(num == rootValue){
                flag = 1
                continue
            }
            
            if flag == -1 {
                inorderLeft.append(num)
            } else {
                inorderRight.append(num)
            }
        }
        
        let leftTreeCount = inorderLeft.count
        var leftSum = 0
        for (index,num) in preorder.enumerated() {
            if(index == 0){
                continue
            }
            if(leftSum < leftTreeCount){
                preorderLeft.append(num)
                leftSum += 1
            }
            else{
                preorderRight.append(num)
            }
        }
        
        let rootNode = TreeNode.init(rootValue)
        // 递归构建左子树和右子树
        let leftNode = buildTree(preorderLeft,inorderLeft)
        let rightNode = buildTree(preorderRight,inorderRight)
        rootNode.left = leftNode
        rootNode.right = rightNode
        return rootNode
    }
}
class Solution {
    var combinationSumResult = [[Int]]()
    var combinationSumPaths = [Int]()
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        
        for i in 0..<candidates.count {
            combinationSumDFS(candidates, i, target)
        }
        
        return combinationSumResult
    }
    
    func combinationSumDFS(_ candidates: [Int],_ index:Int, _ target: Int) {
        
        if index > candidates.count - 1 {
            return
        }
        
        // 由于数组的值 > 0, 进行剪枝
        if target < 0 {
            return
        }
        
        combinationSumPaths.append(candidates[index])
        
        if candidates[index] == target {
            combinationSumResult.append(combinationSumPaths)
            combinationSumPaths.removeLast()
            return
        }
        
        let tempTarget = target - candidates[index]
        for i in index..<candidates.count {
            combinationSumDFS(candidates, i, tempTarget)
        }
        
        combinationSumPaths.removeLast()
    }
}

class Solution {
    func romanToInt(_ s: String) -> Int {
        let dict: [Character : Int] = ["I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000]
        var lastNum = 0
        var result = 0
        for c in s {
            let num = dict[c]!
            result += num
            if num > lastNum {
                result -= 2*lastNum
            }
            lastNum = num
        }
        return result
    }
}

func permute(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]()]
    // 初始化为一个空值
    var prev: [[Int]]
    // 当前Int数组
    var cur: [Int]
    // 遍历nums中的每一个元素
    for num in nums {
        // 每轮循环前，用prev装旧值，result清空
        prev = result
        result = [[Int]]()
        // 遍历旧值
        for i in 0..<prev.count {
            // 尝试插入到 previ 中的每一项中去
            for j in 0...prev[i].count {
                cur = prev[i]
                if j < cur.count {
                    cur.insert(num, at: j)
                }else {
                    cur.append(num)
                }
                result.append(cur)
                // print("cur === \(cur),num = \(num), i = \(i), j = \(j)")
            }
            // print("result === \(result)")
        }
    }
    return result
}

class Solution {
    var result = 1
    func maxDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        next(root?.left, root?.right, 1)
        return result
    }
    func next(_ left: TreeNode?, _ right: TreeNode?, _ index: Int)  {
        if left == nil && right == nil {
            if index > result {
                result = index
            }
            return
        }
        if left != nil {
            let value = index + 1
            next(left?.left, left?.right, value)
        }
        if right != nil {
            let value = index + 1
            next(right?.left, right?.right, value)
        }
    }
}
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        if head == nil {
            return nil
        }
        if n == 0 {
            return head
        }
        let dummyHead = ListNode(-1, head)
        var fast: ListNode? = dummyHead
        var slow: ListNode? = dummyHead
        // fast 前移 n
        for _ in 0 ..< n {
            fast = fast?.next
        }
        while fast?.next != nil {
            fast = fast?.next
            slow = slow?.next
        }
        slow?.next = slow?.next?.next
        return dummyHead.next
    }
}
func sortColors(_ nums: inout [Int]) {
    var i = 0
    var left = 0
    var right = nums.count-1
    while i <= right {
        let value = nums[i]
        if value == 0 {
            nums[i] = nums[left]
            nums[left] = value
            i += 1
            left += 1
        } else if value == 1 {
            i += 1
        } else {
            nums[i] = nums[right]
            nums[right] = value
            right -= 1
        }
    }
}
class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var i = 0
        var result = 0
        var leftValue = prices[0]
        while i < prices.count {
            if  prices[i] < leftValue {
                leftValue = prices[i]
            } else {
                let value = prices[i] - leftValue
                if value > result {
                    result = value
                }
            }
            i = i + 1
        }
        return result
    }
}

class Solution {
    func reverse(_ x: Int) -> Int {
        var str = String(abs(x))
        var result = ""
        for i in str  {
            result = String(i) + result
        }
        var k:Int = Int(result)!
        k = x > 0 ? k : -k
        if k > Int32.max || k < -Int32.max {
            k = 0
        }
        return k
    }
}

class Solution(object):
def treeToDoublyList(self, root):
#中序遍历的顺序正好是从小到大的
def dfs(cur):
if not cur:return
    dfs(cur.left)
    if self.pre:
        self.pre.right,cur.left = cur,self.pre
    else:
        self.head = cur
    self.pre = cur
    dfs(cur.right)
    
    if not root:return
    self.pre = None
    dfs(root)
    self.head.left,self.pre.right = self.pre,self.head
    return self.head
    
